﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Heap
{

    public class BinaryTree<T>
    {

        private Node[] m_data;
        private int m_size;
        private int m_capacity;

        /**
         * Construct a simple binary tree
         */
        public BinaryTree()
        {
            this.m_capacity = 10;
            this.m_data = new Node[this.m_capacity];
        }

        /**
         * Add a new node with a given key and character
         * @param _key
         * @param _char
         */
        public void AddNode(ConstraintKey _key, T _char)
        {
            if (this.m_capacity <= this.m_size * 2)
            {
                Resize();
            }

            this.m_size++;
            Node tmpNode = new Node(_key, _char, this.m_size - 1);
            this.m_data[this.m_size - 1] = tmpNode;

        }

        /**
         * @param _i
         * @return Returns the node at the specified index
         */
        public Node Get(int _i)
        {
            if (_i >= 0 && _i < this.m_capacity)
                return this.m_data[_i];
            else
                return null;
        }

        /**
         * Set a specific node with the content of another node
         * @param _i
         * @param _node
         */
        public void Set(int _i, Node _node)
        {
            if (_node == null)
            {
                this.m_data[_i] = null;
            }
            else if (_i >= 0 && _i < this.m_capacity)
            {
                this.m_data[_i].setM_Key(_node.getM_Key());
                this.m_data[_i].setM_Value(_node.getM_Value());
            }

        }

        /**
         * @return Returns the root of the binary tree
         */
        public Node getRoot()
        {
            return this.m_data[0];
        }

        /**
         * @param _nodeIndex
         * @return Returns an array of size two with the children nodes of the specified node
         */
        public Node[] getChildren(int _nodeIndex)
        {
            Node[] tmp = new Node[2];
            tmp[0] = this.m_data[2 * _nodeIndex + 1];
            tmp[1] = this.m_data[2 * _nodeIndex + 2];

            return tmp;
        }

        /**
         * 
         * @param _node
         * @return True if the node has a left child
         */
        public bool hasLeft(int _node)
        {
            return (this.m_data[_node * 2 + 1] != null) ? true : false;
        }

        /**
         * 
         * @param _node
         * @return True if the node has right child
         */
        public bool hasRight(int _node)
        {
            return (this.m_data[_node * 2 + 2] != null) ? true : false;
        }
        /**
         * 
         * @param _node
         * @return True if the node has a right or left child or both
         */
        public bool hasChildren(int _node)
        {
            return (hasLeft(_node) && hasRight(_node)) ? true : false;
        }
        /**
         * 
         * @param _node
         * @return True if the node has children
         */
        public bool isInternal(int _node)
        {
            return ((this.m_data[_node * 2 + 2] != null) || (this.m_data[_node * 2 + 1] != null)) ? true : false;
        }
        /**
         * 
         * @param _node
         * @return True is the node is a leaf
         */
        public bool isExternal(int _node)
        {
            return ((this.m_data[_node * 2 + 2] != null) && (this.m_data[_node * 2 + 1] != null)) ? true : false;
        }

        /**
         * 
         * @param _node
         * @return True if the node is the root of the binary tree
         */
        public bool isRoot(int _node)
        {
            return (_node == 0) ? true : false;
        }

        /**
         * 
         * @param _nodeIndex
         * @return Return the left child node of the specified index otherwise returns null
         */
        public Node getLeftChild(int _nodeIndex)
        {
            return (2 * _nodeIndex + 1 < this.m_capacity) ? this.m_data[2 * _nodeIndex + 1] : null;
        }
        /**
         * 
         * @param _nodeIndex
         * @return Return the right child node of the specified index otherwise returns null
         */
        public Node getRightChild(int _nodeIndex)
        {
            return (2 * _nodeIndex + 2 < this.m_capacity) ? this.m_data[2 * _nodeIndex + 2] : null;
        }

        /**
         * 
         * @param _nodeIndex
         * @return Returns the parent of the specified node
         */
        public Node getParent(int _nodeIndex)
        {
            return this.m_data[(_nodeIndex - 1) / 2];
        }


        /**
         * 
         * @return Returns the size of the binary tree
         */
        public int getM_size()
        {
            return m_size;
        }

        /**
         * Set the size of the binary tree
         * @param m_size
         */
        public void setM_size(int m_size)
        {
            this.m_size = m_size;
        }
        /**
         * 
         * @return Returns the capacity of the binary tree
         */
        public int getM_capacity()
        {
            return m_capacity;
        }



        /**
         * Resize the array (tree) by doubling its size
         */
        private void Resize()
        {
            Node[] tmpArray = new Node[this.m_capacity * 2];

            for (int i = 0; i < this.m_size; i++)
            {
                tmpArray[i] = this.m_data[i];
            }

            this.m_capacity *= 2;
            this.m_data = tmpArray;
        }



    }

}
